import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * @Author ZhangCuirong
 * @Date 2025/9/18 8:22
 * @description:
 */
public class LCR170 {
    int[] temp;
    int[] counts;//用于记录每个元素右侧小于它的个数
    int[] indexes;//用于记录元素的原始索引，用于跟踪位置

    public int reversePairs(int[] record) {
        if (record == null || record.length == 0) {
            return 0;
        }
        temp = new int[record.length];
        counts = new int[record.length];
        indexes = new int[record.length];
        for (int i = 0; i < record.length; i++) {
            indexes[i] = i;
        }
        mergeSort(record, 0, record.length - 1);
        int count = 0;
        for (int i = 0; i < counts.length; i++) {
            count += counts[i];
        }
        return count;
    }

    public void mergeSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, mid + 1, right);
    }

    public void merge(int[] nums, int l1, int r1, int l2, int r2) {
        if (l1 > r1 || l2 > r2) {
            return;
        }
        int p1 = l1, p2 = l2;
        int index = l1;
        while (p1 <= r1 && p2 <= r2) {
            if (nums[indexes[p1]] <= nums[indexes[p2]]) {//小于等于的时候判断，如果大于的时候判断会重复
                counts[indexes[p1]] += (p2 - l2);
                temp[index++] = indexes[p1++];
            } else {
                temp[index++] = indexes[p2++];
            }
        }
        while (p1 <= r1) {
            counts[indexes[p1]] += (p2 - l2);
            temp[index++] = indexes[p1++];
        }
        while (p2 <= r2) {
            temp[index++] = indexes[p2++];
        }
        for (int i = l1; i <= r2; i++) {
            indexes[i] = temp[i];
        }
    }

    public static void main(String[] args) {
        LCR170 lcr = new LCR170();
        System.out.println(lcr.reversePairs(new int[]{9, 7, 5, 4, 6}));
        System.out.println(lcr.reversePairs(new int[]{5, 2, 6, 1}));
    }
}
